Undo/redo functionality is a common feature of various interactive applications and systems. Most applications provide a mechanism for the user to undo an action, and then redo it if they change their mind about undoing the action. This is a fairly ubiquitous feature and one that users have come to expect when working on their documents or data in most user applications.
Most applications today use a very simple undo/redo model. All actions are stored in a history buffer (e.g., stack buffer). The most recent action may be undone by performing an inverse operation. Such an action is marked as undone and the user may redo it, or may further undo the previous action. This simple model, commonly known as linear undo model, is sufficient in many applications. The result of undo/redo operations may be easily predicted and also the physical implementation is not very complex.
Two architectural approaches exist for implementing undo/redo functions in an application. They include an action-based approach and a model-based approach. In the action-based approach, each action specifies a reverse action that can be applied to undo the action, e.g., if a user types in a word in a word processor, the reverse of that action is to delete the word. When the action is undone, the word is deleted, and when the action is redone, the word reappears again. This approach usually requires that the reverse action be implemented along with the original action.
In the model-based approach, on the other hand, each action modifies a central model that is a representation of the object (e.g., document) being worked on. A snapshot of the model is taken after every action and can be stored in memory. When performing an undo operation, the most recent snapshot of the central model is retrieved from memory. This approach requires that the application have some mechanism to store the model and to set its internal state based on the contents of the model.
Problems arise with the action-based approach when attempting to integrate an undo/redo feature into an already mature product with hundreds or thousands of existing actions. Using the action-based approach with a mature product is much more difficult as it requires adding a reverse action for each and every action. In addition, the biggest challenge with using the model-based approach is memory consumption. A representation of the entire document or object must be stored in memory for each and every action. This can rapidly become onerous and is generally not scalable for large documents.
One strategy to minimize memory consumption is to store only the changes, or differences (or deltas) between successive states of the object mode such that the entire model is not replicated, but only the sections of the model that were changed in between states. However, this strategy is not free and adds the computational expense of calculating the deltas in a fast and efficient manner. The nature of the computer language being used bears on the problem as well, since different languages expose different mechanisms for dealing with objects and equality. A model-based undo architecture in a language that has runtime dynamic polymorphism (“RDP”) is both memory-intensive and computationally expensive.
Javascript (which is the language usually used for web applications on the Internet) exhibits RDP, unlike statically compiled languages like C or C++. RDP indicates that the members and properties of a Javascript object can be changed at runtime, unlike in C or C++ or Java, where a class's members and methods are known at compile time and cannot be changed at runtime. For example, the class “C” below coded in Javascript can be modified to have a new member “C.gamma” during program execution, while the class “J” coded in Java below cannot be modified to have a new member at runtime, since Java simply does not support changing class templates at runtime. Adding the member gamma to the Java class J would require modifying the class definition, and then recompiling the class and running it again.
JavascriptJavaC : {Class J {alpha : 1,int alpha = 1;beta : trueboolean beta = true;}}C.gamma = “abc”;J j = new J( )j.gamma = “abc”; //This is impossible andwill not compile
Thus if two objects in Javascript point to the same location in memory, they are considered equal. But if they don't point to the same memory location, then a deeper equality check of the Javascript objects is required, since it is quite possible for an object to have been modified at runtime to contain a new property at some level. This requires a deep, recursive equality check of two Javascript objects to guarantee the two Javascript objects are equal. This is computationally expensive.